import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-06-19
 * Time: 14:10
 */
public class TestDemo {


    public static void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    //选择排序
    public static void selectSort(int[] array){
        //从数组中选择一个最小的数字,然后遍历的下标进行交换
        for(int i =0;i<array.length;++i){
            int minIndex = i;
            for(int j =i+1;j<array.length;++j){
                if(array[j]<array[minIndex]){
                    minIndex =j;
                }
            }
            swap(array,i,minIndex);
        }
    }

    //冒泡排序
    public static void bubbleSort(int[] array){
        for(int i =0;i<array.length-1;++i){
            boolean flag = true;
            for(int j =0;j<array.length-1-i;++j){
                if(array[j]>array[j+1]){
                    swap(array,j+1,j);
                    flag = false;
                }
            }
            if(flag){
                return;
            }
        }
    }

    public static void InsertSort(int[] array){
        for(int i =1;i<array.length;++i){
            int tmp = array[i];
            int j =i-1;
            for(;j>=0;--j){
                //i前面的元素就是有序的，我们将i位置的元素插入到i位置的前面
                if(array[j]>tmp) {
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

    private static void shell(int[] array,int gap){
        for(int i =1;i<array.length;++i){
            int tmp = array[i];
            int j = i-gap;
            for(;j>=0;j-=gap){
                if(array[j]>tmp){
                    array[j+gap] = array[j];
                }else {
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }

    public static void shellSort(int[] array){
        int gap = array.length;
        while(gap>1){
            shell(array,gap);
            gap/=3;
        }
        shell(array,1);
    }

    private static void shiftDown(int[] array,int parent,int len){
        int child = 2*parent+1;//左孩子
        while(child<len){
            //找左右孩子中节点最大的
            if(child+1<len&&array[child]<array[child+1]){
                child++;
            }
            //此时child是左右孩子当中最大的节点
            //在与parent进行比较
            if(array[parent]<array[child]){
                swap(array,parent,child);
            }else {
                break;
            }
            //更新左右孩子节点
            parent = child;
            child= 2*parent+1;
        }
    }

    //首先我们要将元素建成大堆
    private static void createHeap(int[] array){
        //要将每一个子树建成大堆
        for(int p = (array.length-1-1)/2;p>=0;p--){
            shiftDown(array,p,array.length);
        }
    }

    public static void heapSort(int[] array){
        createHeap(array);
        for(int end = array.length-1;end>=0;end--){
            swap(array,0,end);
            shiftDown(array,0,end);
        }
    }
    //hoare法
    public static int quick1(int[] array,int left,int right){
        int pivot = left;
        //右边找小，左边找大
        while(left<right){
            //右边找小
            while(left<right&&array[right]>=array[pivot]){
                right--;
            }
            //左边开始找大
            while(left<right&&array[left]<=array[pivot]){
                left++;
            }
            swap(array,left,right);
        }
        //此时left和right指向相同的元素
        swap(array,pivot,left);
        return left;
    }

    public static void quickSort1(int[] array,int left,int right){
            if(left>=right){
                return;
            }
          int mid = quick1(array,left,right);
          quickSort1(array,left,mid-1);
          quickSort1(array,mid+1,right);
    }
    //挖坑法
    public static int quick2(int[] array,int left,int right){
           int pivot = array[left];
           while(left<right){
               //右边找小放大左边
               while(left<right&&array[right]>=pivot){
                   right--;
               }
               array[left] = array[right];
               while(left<right&&array[left]<=pivot){
                   left++;
               }
               array[right] = array[left];
           }
           //此时两者相遇了
           array[left] = pivot;
           return left;
    }

    public static void quickSort2(int[] array,int left,int right){
        if(left>=right){
            return;
        }
        int mid = quick2(array,left,right);
        quickSort2(array,left,mid-1);
        quickSort2(array,mid+1,right);
    }
    //前后指针法
    public static int quick3(int[] array,int left,int right){
         int prev = left;
         int cur = left+1;
         int pivot = left;
         while(cur<=right){
            if(array[cur]<array[pivot]&& ++prev!=cur){
                swap(array,cur,prev);
            }
            cur++;
         }
         swap(array,prev,pivot);
         return prev;
    }

    public static void quickSort3(int[] array,int left,int right){
        if(left>=right){
            return;
        }
        int mid = quick3(array,left,right);
        quickSort3(array,left,mid-1);
        quickSort3(array,mid+1,right);
    }

    public static void MergeSort(int[] array){

    }


    public static void main(String[] args) {
        int[] array = new int[]{6,1,2,7,9,3,4,5,10,8};
//       selectSort(array);
//        System.out.println(Arrays.toString(array));
//        bubbleSort(array);
//        System.out.println(Arrays.toString(array));
//        InsertSort(array);
//        System.out.println(Arrays.toString(array));
//        shellSort(array);
//        System.out.println(Arrays.toString(array));
//        heapSort(array);
//        System.out.println(Arrays.toString(array));
         // quickSort1(array,0,array.length-1);
         // quickSort2(array,0,array.length-1);
//        quickSort3(array,0,array.length-1);
//        System.out.println(Arrays.toString(array));
        MergeSort(array);
        System.out.println(Arrays.toString(array));

    }

    //取前k个最小的元素
    public static int[] topK(int[] array,int k){
        if(k==0){
            return new int[k];
        }
        //建造一个大堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k,new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        //我们要先建造一个k大小的堆
        int i =0;
        for(i=0;i<k;++i){
            maxHeap.offer(array[i]);
        }
        //此时i指向的元素就是第四个元素
        //因为我们要找前k个最小的元素所以如果碰见这个元素大于堆顶元素，
        //那么这个元素一定不是前k个最小的元素如果这个元素小于堆顶元素，那么就将对顶元素弹出然后将这个元素加入堆中
        for(;i<array.length;++i){
            int temp = maxHeap.peek();
            if(array[i]<temp){
                maxHeap.poll();
                maxHeap.offer(array[i]);
            }
        }
        int[] ret = new int[k];
        for(int j =0;j<k;++j){
            ret[j]=maxHeap.poll();
        }
         return ret;
    }

    //取前k个最小的元素
    public static int topKWords(int[] array,int k){
        if(k==0){
            return -1;
        }
        //建造一个大堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k,new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        //我们要先建造一个k大小的堆
        int i =0;
        for(i=0;i<k;++i){
            maxHeap.offer(array[i]);
        }
        //此时i指向的元素就是第四个元素
        //因为我们要找前k个最小的元素所以如果碰见这个元素大于堆顶元素，
        //那么这个元素一定不是前k个最小的元素如果这个元素小于堆顶元素，那么就将对顶元素弹出然后将这个元素加入堆中
        for(;i<array.length;++i){
            int temp = maxHeap.peek();
            if(array[i]<temp){
                maxHeap.poll();
                maxHeap.offer(array[i]);
            }
        }
        return maxHeap.peek();
    }

    public static void main1(String[] args) {
        int[] array = new int[]{9,6,5,8,0,2,6,7,15};
        int[] ret = topK(array,3);
        System.out.println(Arrays.toString(ret));
        System.out.println(topKWords(array,3));
    }


}
